\documentclass[12pt]{article}
\usepackage{calc,fancyhdr}
\usepackage[hmargin=.5in,vmargin=.75in,
            footskip=.25in,headsep=.5in-\headheight]{geometry}

% Template solution to Exercise 5.

% Common formatting macros for CSC165.
\usepackage{amsmath,amssymb}
\input{macros-165}

% Page layout: stretch text to fill up page.
\flushbottom

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{CSC\,165\,H1S}
\chead{Homework Exercise \#\,8}
\rhead{Winter 2014}

\begin{document}

\begin{large}
  \noindent
  Name: Robert Staskiewicz \hfill CDF login name: c3staski\\[0.5cm]
  Partner: Ekam Shahi    \hfill CDF login name: c3shahie
\end{large}

\medskip

\noindent
\rule{\textwidth}{.5pt}

\subsection*{Topic: Algorithm Analysis}

\medskip

\begin{enumerate}
 
       
    % place solution to question 1 below

    \item
    \begin{enumerate}
    % place solution to question 2 below
    
    
        	\item 
            \medskip
            \noindent
            Consider the following definition of $f(n) \in \Theta(g(n))$:
            \begin{quote}
            $${\exists c_1\in \R^+,\exists c_2 \in \R^+, \exists B \in \N, \forall n \in \N, (n \geq B) \implies(c_1g(n)\leq f(n)\leq c_2g(n))} $$
            \end{quote}

            {\bf Proof:} 
            \begin{pindent}
                    	 Lines 1-4 take 4 steps.\\
                    	            Line 6 iterates at most n times.\\
                    	            Line 7 executes at most $\frac{n(n+1)}{2}$ times \just{Triangular number series}\\
                    	   			Line 8 executes at most n times.\\
                    	   			We have a rough estimate of $f(n) = \frac{n(n+1)}{2} + n + n + 4$\\
                    	   			Which simplifies to $f(n) = \frac{n^2+n+2n+2n+8}{2}$\\
                    	   			Which further simplifies to $ f(n) = \frac{n^2+5n+8}{2}$\\
           
        
        	We must first show that $f(n) \in \mathcal{O}(n^2)$\\\\
        	Let $c' = 2$ and $ B'= 1 $\\
        	Then $c' \in \R^+ $ and $B' \in \N$\\
        	Assume $n \in \N $ and $ n \geq B'$\\
        	Then $f(n) = \frac{n^2+5n+8}{2} < 2(\frac{n^2+5n+8}{2})= n^2+5n+8=2f(n) $\\
        	Then $f(n) \leq 2g(n^) $ \just{Let $f(n)=g(n)$}\\
        	Then $f(n) \leq c'g(n) $ \just{$f(n)$ is the number of steps taken by the algorithm on input n }\\
        	Then $\forall n \in \N, (n \geq B') \implies (f(n) \leq c'g(n) )$\\
        	Therefore, $\exists c_2 \in \R^+, \exists B \in \N, \forall n \in \N, (n \geq B) \implies (f(n) \leq c_2g(n^2))$\\
        	
        	We must now show that $f(n) \in \Omega(n^2) $\\
        	
        	Let $c' = \frac{1}{2}$ and $ B'= 1 $\\
        	Then $c' \in \R^+ $ and $B' \in \N$\\
        	Assume $n \in \N $ and $ n \geq B'$\\
        	Then $f(n) = \frac{n^2+5n+8}{2} > \frac{1}{2}(\frac{n^2+5n+8}{2})= \frac{n^2+5n+8}{4}= \frac{1}{2}f(n)  $\\
        	Then $f(n) \leq 2g(n^) $ \just{Let $f(n)=g(n)$}\\
        	Then $f(n) \leq c'g(n) $ \just{$f(n)$ is the number of steps taken by the algorithm on input n }\\
        	Then $\forall n \in \N, (n \geq B') \implies (f(n) \geq c'g(n) )$\\
        	Therefore, $\exists c_1 \in \R^+, \exists B \in \N, \forall n \in \N, (n \geq B) \implies (f(n) \geq c_1g(n^2))$\\
                
                % $ \ \forall n \in \Z,\ \sum_{1}^{i} (2n-1) \equiv n^2  $
            \end{pindent}
            \medskip
            
            We have shown $[f(n) \in \Omega(n^2)] \land [f(n) \in \mathcal{O}(n^2)] $, which is the definition of a Theta-Oh.\\ Therefore, the tight-bound is $f(n) \in \Theta(n^2)$
                
	\end{enumerate}
    \item
    Consider the following formal definition of $f(n) \in \Theta(g(n))$:
    \begin{quote} 
        $${\exists c_1\in \R^+,\exists c_2 \in \R^+, \exists B \in \N, \forall n \in \N, (n \geq B) \implies(c_1g(n)\leq f(n)\leq c_2g(n))} $$
    \end{quote}
    {\bf Proof:}
    \begin{pindent}
    Line 1 is 1 step.\\
    Line 2 is n steps.\just{The algorithm is iterating through n backwards}\\
    Line 3 is n steps.\\
    Line 4 is n steps. \just{iterating over a list of length n}\\
    For line 4, the algorithm's worst case is executing line 5, n times \just{If there is no $a[i] > a[i+1]$}\\
    Line 10 executes once for each time in Line 2.\\
    This leaves us with a rough estimate of $f(n)=5n*n+n+n+1$\\
    This simplifies to $f(n) = 5n^2+2n+1$\\
    
    We must first show that $f(n) \in \mathcal{O}(n^2)$\\\\
            	Let $c' = 6$ and $ B'= 2 $\\
            	Then $c' \in \R^+ $ and $B' \in \N$\\
            	Assume $n \in \N $ and $ n \geq B'$\\
            	Then $5n^2\leq 6n^2 $\\
            	Then $5n^2 \leq 5n^2 + n\leq 6n^2 $\just{$n < n^2$, for $n\geq 2$} \\
            	Then $5n^2+n\leq 5n^2+n+n\leq 6n^2 $\just{$ 2n\leq n^2$, for $n\geq 2$}\\
            	Then $f(n) = 5n^2+2n+1 < 6n^2 = g(n) $\\
            	Then $f(n) \leq 6g(n^) $ \\
            	Then $f(n) \leq c'g(n) $ \just{$f(n)$ is the number of steps taken by the algorithm on input n }\\
            	Then $\forall n \in \N, (n \geq B') \implies (f(n) \leq c'g(n) )$\\
            	Therefore, $\exists c_2 \in \R^+, \exists B \in \N, \forall n \in \N, (n \geq B) \implies (f(n) \leq c_2g(n^2))$\\
            	
            	We must now show that $f(n) \in \Omega(n^2) $\\
            	        	
            	        	The loop on Line 2 executes at least n times\\
            	        	The loop on Line 3 executes at least n times\just{Even if we swap, the comparison must be made}\\
            	        	Let $c' = 5$ and $ B'= 1 $\\
            	        	Then $c' \in \R^+ $ and $B' \in \N$\\
            	        	Assume $n \in \N $ and $ n \geq B'$\\
            	        	Then $f(n) =  5n^2\leq 5n^2+2n+1 $\just{$B'\geq1$} \\
            	        	Then $f(n) \leq 5g(n^)$\\
            	        	Then $f(n) \leq c'g(n) $ \just{$f(n)$ is the number of steps taken by the algorithm on input n }\\
            	        	Then $\forall n \in \N, (n \geq B') \implies (f(n) \geq c'g(n) )$\\
            	        	Therefore, $\exists c_1 \in \R^+, \exists B \in \N, \forall n \in \N, (n \geq B) \implies (f(n) \geq c_1g(n^2))$\\
            	        	
            	            We have shown $[f(n) \in \Omega(n^2)] \land [f(n) \in \mathcal{O}(n^2)] $, which is the definition of a Theta-Oh.\\ Therefore, the tight-bound is $f(n) \in \Theta(n^2)$
            	                
            	                
        \end{pindent}
        \medskip
        
       


\end{enumerate}

\noindent
\rule{\textwidth}{.5pt}

\end{document}
